#include "..\CookHeader.h"

int ROW=5,  COL = 5;
Array <Array <int>> goldMaze = { {1, 4, 4, 2, 2},
								 {1, 3, 3, 0, 5},
								 {1, 2, 4, 3, 0},
								 {3, 3, 0, 4, 2},
								 {1, 3, 4, 5, 3} };

int growRich() {
	Array <Array <int>> memo = emptyArray2(ROW, COL); // 5X5  迭
	memo[0][0] = goldMaze[0][0];

	int rowSum = memo[0][0];
	for (int i = 1; i < ROW; i++) {
		rowSum += goldMaze[0][i];
		memo[0][i] = rowSum;
	}

	int colSum = memo[0][0];
	for (int i = 1; i < COL; i++) {
		colSum += goldMaze[i][0];
		memo[i][0] = colSum;
	}

	for (int row = 1; row < ROW; row++) {
		for (int col = 1; col < COL; col++) {
			if (memo[row][col - 1] > memo[row - 1][col])
				memo[row][col] = memo[row][col - 1] + goldMaze[row][col];
			else
				memo[row][col] = memo[row-1][col] + goldMaze[row][col];
		}
	}

	return memo[ROW-1][COL-1];
}

int main() {
	int macolGold = growRich();
	println("\nȲ ̷ο  ִ Ȳ  -->" + to_string(macolGold));
}